package problem;

import java.util.*;

/**
 * @author RunningShrimp
 * @date 2021/5/24  20:00
 * @see <a href="https://leetcode-cn.com/problems/top-k-frequent-elements/">347. 前 K 个高频元素</a>
 */
public class TopKFrequentElements {


    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>(nums.length);
        for (int num : nums) {
            if (map.containsKey(num)) {
                int time = map.get(num) + 1;
                map.put(num, time);
            } else {
                map.put(num, 1);
            }
        }
        Queue<Freq> priorityQueue = new PriorityQueue<>(nums.length);
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            priorityQueue.add(new Freq(entry.getKey(), entry.getValue()));
        }
        int[] result = new int[k];
        for (int i = 0; i < k; i++) {
            result[i] = Objects.requireNonNull(priorityQueue.poll()).e;
        }
        return result;
    }

    public int[] topKFrequent1(int[] nums, int k) {
        Map<Integer, Integer> map = new HashMap<>(nums.length);
        for (int num : nums) {
            if (map.containsKey(num)) {
                int time = map.get(num) + 1;
                map.put(num, time);
            } else {
                map.put(num, 1);
            }
        }
        Queue<Integer> pq = new PriorityQueue<>((a, b) -> map.get(b) - map.get(b));
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {

            if (pq.size() < k) {
                pq.add(entry.getKey());
            } else if (entry.getValue() > pq.peek()) {
                pq.remove();
                pq.add(entry.getKey());
            }
        }
        int[] result = new int[k];
        for (int i = 0; i < k; i++) {
            result[i] = pq.remove();
        }
        return result;
    }


    private class Freq implements Comparable<Freq> {
        int e, freq;

        public Freq(int e, int freq) {
            this.e = e;
            this.freq = freq;
        }

        @Override
        public int compareTo(Freq another) {
            return Integer.compare(another.freq, this.freq);
        }
    }
}
